// 时间复杂度与空间复杂度

// 1.1 时间复杂度

var persons = [
    {name:"xxx",age: 13},{name:"yyy",age: 14},
    {name:"pat",age: 9},{name:"nasami",age: 22},
    // ...
];

// 时间复杂度O(n)
for (let i = 0, n = persons.length; i < n; i++) {
    if (persons[i].name === "司徒正美") {
      console.log(persons[i].age);
      break;
    }
}

// 常数阶O(1) < 对数阶O(logn) < 线性阶O(n) < 线性对数阶O(nlogn) < 平方阶O(n2) < 立方阶O(n3) < k次方阶O(nk) < 指数阶O(2n) < 阶乘阶O(n!)

// 1 线性阶

let a = 0, b = 1; // 语句①
for(let i = 1; i < n; i++){// 语句②，语句③，语句④
  s = a + b;// 语句⑤
  b = a; // 语句⑥
  a = s; // 语句⑦
};

// (1)	分别计算每条语句的执行次数，得到语句的总执行次数：
// T(n) = 1 + 1 ＋ n + (n-1) + (n-1) + (n-1) + (n-1)
//      = 2 + n + 4n - 4;
//      = 5n - 2
// (2)	用1代替常数项2，得到5n+1。
// (3)	只保留最高阶项，所以去掉常数项+1，得到5n。
// (4)	去掉与最高阶项相乘的常数，得到n。用大O法表示，我们可以得到示例代码的时间复杂度为O(n)。

// 2. 对数阶
var number = 1; // 语句①
while(number < n) {// 语句②
  number = number * 2;// 语句③
}
// 语句③比语句②少执行1次
// 计算多少个2相乘后大于n，因为这时候会退出循环。由2x=n可以得到x=log2n
// 语句②的执行次数为log2n
// T(n) = 1 + log2n + log2n-1 = 2log2n = log2n

// 3. 平方阶 

// 双层循环结构，冒泡排序也是这样的结构：
for (let i = 0; i < n; i++) {   
  for (let j = i; j < n; j++) {
    // 复杂度为O(1)的算法
    // ……
  }
}

// T(n) = n + (n-1) + (n-2) + (n-3) +…+1 
//      = (n+1) + [(n-1) + 2] + [(n-2) + 3] + [(n-3) + 4]+…
//      = (n+1) + (n+1) + (n+1) + (n+1) +…
//      = (n+1) n / 2 
//      = n(n+1) / 2 
//      = n2/2 + n/2
// 到n2/2，再去掉常数乘数，最后得到这个循环的时间复杂度为O(n2)。


// 4. 立方阶
// 三重循环，每一重的起点依赖于上一重的变量
for (i = 1; i <= n; ++i) { // 第一重循环
    for (j = 1; j <= n; ++j) { // 第二重循环
      for (k = 1; k <= n; ++k) { // 第三重循环
        // 复杂度为O(1)的算法
        // ……
      }
    }
  } 

//   5. 指数阶
// 斐波那契数列（Fibonacci sequence）
function fibonacci(n) {
    if(n <= 1){
      return 1;
    } else {
      return fibonacci(n-1) + fibonacci(n-2);
    }
  }

// 当n=40时，Chrome出现了明显卡顿
//   f(40)
//   /         \
// f(39)         f(38)
// /    \        /    \
// f(38)   f(37)  f(37)  f(36)
//      . . .
// f(2)     
// /  \ 
// f(1)  f(0)  
// 求取f(40)，会转换为f(39)与f(38)的求取结果相加，以此类推，最终都会抵达f(2)=f(1)+f(0)=
// 1+1=2，故可获得f(40)的结果。
// 对于斐波那契的时间复杂度的计算，可采取母函数法获取。更详细的资料大家可自行在互联网上查找。


// 1.2　空间复杂度
// ，空间复杂度（space complexity）是对一个算法在运行过程中临时占用存储空间大小的量度。


// 给定一个整数数组nums和一个整数目标值target，请你在该数组中找出“和”为目标值target的那两个整数，并返回它们的数组下标
// 方法一：暴力枚举 时间复杂度为O(n2) 空间复杂度为O(1) 采用“就地”存储
var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
      for (let j = i + 1; j < nums.length; j++) {
        if (target - nums[i] === nums[j]) {
          return [i, j];
        }
      }
    }
    console.log("No two sum solution");
};
// 方法二：散列表 散列表进行元素存储 消耗的空间复杂度为O(n) 时间复杂度的消耗，此处为O(n)。
var twoSum = function(nums, target) {
    var map = new Map();
    for (let i = 0; i < nums.length; i++) {
      let complement = target - nums[i];
      if (map.has(complement)) {
        return [map.get(complement), i];
      }
      map.set(nums[i], i);
    }
    console.log("No two sum solution");
};

// 交换两个整数变量

var x =5, y=10; // 定义两个变量
// 方式1
var temp = x;;    // 定义临时变量temp并提取x值
var x = y;;       // 把y的值赋给x
var y = temp;;    // 然后把临时变量temp的值赋给y
// 方式2
x = x + y;        // x(15) = 5 + 10
y = x - y;        // y(5) = x(15) - 10       
x = x - y;        // x(10) = x(15) - y(5)
// 方式3
x = x^y;
y = x^y;  // y=(x^y)^y
x = x^y;  // x=(x^y)^x


// 合并两个有序数组，要求时间复杂度为O(n)，空间复杂度为O(1)。

var src = [1,1,1,1,1,1,3,5,7,9];        
var dest = [2,4,6,8,10,12];
function mergeArray(src, dest, n, m) {
  var indexOfNew = n + m - 1; // 新数组的末位索引
  var indexOfSrc = n - 1; // src有效元素的末位索引
  var indexOfDest = m - 1; // dest有效元素的末位索引
  // 当dest全部扫描完成，元素全部插入src，剩余src元素不需要移位操作
  // 当src全部遍历完成，但dest仍有元素时，只需要操作dest即可，此时src下标已达最小值0
  while (indexOfDest >= 0) {
    if (indexOfSrc >= 0) {
      // 将src或dest中较大的元素放入src的后几位中去
      if (src[indexOfSrc] >= dest[indexOfDest]) {
        src[indexOfNew] = src[indexOfSrc];
        --indexOfNew;
        --indexOfSrc;
      } else {
        src[indexOfNew] = dest[indexOfDest];
        --indexOfNew;
        --indexOfDest;
      }
    } else { // 如果dest比较长，那么挪动dest到indexOfNew位置上
      src[indexOfNew] = dest[indexOfDest];
      --indexOfNew;
      --indexOfDest;
    }
  }
}
console.log(src);